package com.shuang.stack4;

import java.util.Stack;

class Solution {
    //单调栈解法（横向一层一层的寻找雨水）
    //遍历到的值大于栈顶下标对应的值时说明遍历值为凹槽（中间值下标）右边第一个大的值，而左边第一个大的值就是栈顶的下一个元素（单调递增的栈）
    // 比中间大的值左右两边的值中较小的那个减去中间值即为当前层的水的高度h 再用右边下标减去左边下标-1即为水的宽度相乘求和即可
    public int trap(int[] height) {

        //用于存放计算结果
        int sum = 0;
        //定义栈
        Stack<Integer> st = new Stack<>();
        st.push(0);

        for (int i = 1; i < height.length; i++) {
            //三种情况
            if (height[i] < height[st.peek()]) {
                st.push(i);
            } else if (height[i] == height[st.peek()]) {
                //将旧的值弹出将新的值加进去 直接加进去也可以会有重复的为0的计算结果
                st.pop();
                st.push(i);
            } else {
                while (!st.isEmpty() && height[i] > height[st.peek()]) {
                    //先将栈顶弹出并记录下来 作为中间值的下标 然后栈顶就变成了中间值的左边第一个大的数了
                    int midIndex = st.pop();

                    //判断不空的时候才计算
                    if (!st.isEmpty()) {
                        //当前遍历到的数就是比中间值第一个大的右边的数
                        //计算高度
                        int h = Math.min(height[st.peek()], height[i]) - height[midIndex];

                        //计算宽度
                        int width = i - st.peek() - 1;
                        //计算最后结果
                        sum += h * width;
                    }

                }

                st.push(i);
            }
        }

        return sum;
    }
}